local algorithm		= require "algorithm"
local hash          = algorithm.murmur_hash

local M={}
local meta={}
local math=math
meta.__index=meta

local function cmp(a,b)
    return a.hash<b.hash
end

function meta:add_node(node_key,value)
    for i=1,self._vnum do
        local o={node_key=node_key,value=value,hash=hash(node_key.."@"..i)}
        table.insert(self._nodes,o)
    end
    self._vals[node_key]=value
    table.sort(self._nodes,cmp)
end

function meta:remove_node(node_key)
    local list={}
    for k,v in ipairs(self._nodes) do
        if v.node_key ~= node_key then
            table.insert(list,v)
        end
    end
    self._vals[node_key]=nil
    self.__nodes=list
end

function meta:get(key)
    local list=self._nodes
    if not next(list) then return end
    local h=hash(key)
    local s=1
    local e=#list
    local index 
    local o
    if h > list[e].hash or h<=list[1].hash then
        o=list[1]
    else
        while s <= e do
            index = math.modf((s+e)/2+0.1)
            local h2=list[index].hash
            if  h==h2 then
                o=list[index]
                break
            end
            if h < h2 then
                o=list[index]
                e=index-1
            else
                s=index+1
            end
        end
        if not o then o=list[#list] end
    end
    --print("get:",key,h,o.node_key,o.hash)
    self._count[o.node_key]=(self._count[o.node_key] or 0)+1
    return o.value
end

function meta:info()
    local o={vnum=self._vnum,node_num=#self._nodes,count=self._count}
    return o
end

--vnum每个node的虚拟节点数
function M.new(vnum)
    local o={_vnum=vnum,_nodes={},_vals={},_count={}}
    return setmetatable(o,meta)
end

return M